package io.github.hadyang.leetcode.random;

import io.github.hadyang.leetcode.ListNode;
import org.junit.Test;

/**
 * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 *
 * <p>你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * <p>示例 1:
 *
 * <p>给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2:
 *
 * <p>给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorder-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q143 {

  public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head;
    ListNode fast = head;
    ListNode pre = null;

    // 链表分离
    while (fast != null) {
      pre = slow;
      slow = slow.next;

      if (fast.next == null) break;
      fast = fast.next.next;
    }
    pre.next = null;

    // 倒置第二段链表
    fast = slow.next;
    slow.next = null;
    while (fast != null) {
      ListNode next = fast.next;
      fast.next = slow;

      slow = fast;
      fast = next;
    }

    // 链表合并
    while (slow != null) {
      ListNode next1 = head.next;
      ListNode next2 = slow.next;

      head.next = slow;
      slow.next = next1;
      slow = next2;
      head = next1;
    }
  }

  @Test
  public void test1() {
    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);
    ListNode node3 = new ListNode(3);
    ListNode node4 = new ListNode(4);

    node1.next = node2;
    node2.next = node3;
    node3.next = node4;

    reorderList(node1);
  }

  @Test
  public void test2() {
    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);
    ListNode node3 = new ListNode(3);
    ListNode node4 = new ListNode(4);
    ListNode node5 = new ListNode(5);
    ListNode node6 = new ListNode(6);
    ListNode node7 = new ListNode(7);

    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = node6;
    node6.next = node7;

    reorderList(node1);
  }

  @Test
  public void test3() {
    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);

    node1.next = node2;

    reorderList(node1);
  }
}
